#ifndef __ALGORITHM_H_
#define __ALGORITHM_H_

namespace stl
{
//Find value in range
template < typename InputIterator, typename T>
InputIterator 
find ( InputIterator first, InputIterator last, const T& value)
{
    for(; first != last; ++first)
    {
        if(*first == value)
            return first;
    }
    return last;
}

//Find element in range Returns an iterator to the first element in the range [first,last) 
//for which applying pred to it, is true.
template < typename InputIterator, typename Predicate >
InputIterator
find_if ( InputIterator first, InputIterator last, Predicate predicate )
{
    for(; first != last; ++first)
    {
        if( predicate( *first ) )
            return first;
    }
    return last;
}

//Find last subsequence in range
//Searches the range [first1,last1) for the last occurrence of the sequence defined by [first2,last2), and returns an iterator to its first element.
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
find_end ( ForwardIterator1 first1, ForwardIterator1 last1,
            ForwardIterator2 first2, ForwardIterator2 last2 )
{
    if(first2 == last2)
        return last1;

    auto ret = last1;

    while(first1 != last1)
    {
        auto it1 = first1;
        auto it2 = first2;
        while(*it1 == *it2)
        {
            ++it1;
            ++it2;
            if(it2 == last2)
            {
                ret = first1;
                break;
            }
            if(it1 == last1)
                return ret;
        }
        ++first1;
    }
    return ret;
}

template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 
find_end ( ForwardIterator1 first1, ForwardIterator1 last1,
            ForwardIterator2 first2, ForwardIterator2 last2,
            BinaryPredicate pred )
{
    if(first2 == last2)
        return last1;

    auto ret = last1;

    while(first1 != last1)
    {
        auto it1 = first1;
        auto it2 = first2;
        while(pred(*it1, *it2))
        {
            ++it1;
            ++it2;
            if(it2 == last2)
            {
                ret = first1;
                break;
            }
            if(it1 == last1)
                return ret;
        }
        ++first1;
    }
    return ret;
}

//Returns an interator to the first occurrence in the range [first1,last1) of any of the elements in [first2,last2).
template < typename ForwardIterator1, typename ForwardIterator2 >
ForwardIterator1
find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
                ForwardIterator1 first2, ForwardIterator2 last2)
{
    if(first2 == last2) return last1;
    while(first1 != last1)
    {
        auto it = first2;
        while(it != last2)
        {
            if(*first1 == *it)
                return first1;
            ++it;
        }
        ++first1;
    }
    return last1;
}

template < typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate >
ForwardIterator1
find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
                ForwardIterator1 first2, ForwardIterator2 last2,
                BinaryPredicate predicate)
{
    if(first2 == last2) return last1;
    while(first1 != last1)
    {
        auto it = first2;
        while(it != last2)
        {
            if(predicate(*first1,*it))
                return first1;
            ++it;
        }
        ++first1;
    }
    return last1;
}

//Applies function f to each of the elements in the range [first,last).
template < typename InputIterator, typename UnaryFunction >
UnaryFunction
for_each(InputIterator first, InputIterator last, UnaryFunction function)
{
    for(; first != last; ++first)
        function( *first );
    return function;
}

}   //namespace stl


#endif